#include <stdio.h>
#include <stdlib.h>

/**
 * File: Exercise1022.c
 * -------------------------------------------------------
 * 1.22 Modify Program 1.4 to generate random pairs of integers between 0 and `N − 1` instead of reading them from standard input, and
 * to loop until `N − 1` union operations have been performed.
 * Run your program for $N = 10^3, 10^4, 10^5, and 10^6$ and print out the total number of edges generated for each value of N.
 * -------------------------------------------------------
 * 
 */
int main(int argc, char **argv){
    srand((unsigned int)time(NULL));
    int nArray[] = {1000, 10000, 10000, 100000, 1000000};
    int size = sizeof(nArray)/sizeof(int);
    for (int k = 0; k < size; k++) {
        int N = nArray[k];
        int edges = 0;
        int i, p, q, j;
        int id[N];
        int sz[N];

        //初始化id数组值为索引值
        for (i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }

        int unionCount = 0;
        while (unionCount < N-1) {
            p = rand() % N;
            q = rand() % N;
            for (i = p; i != id[i]; i = id[i]) {
                id[i] = id[id[i]];
            }
            for (j = q; j != id[j]; j = id[j]) {
                id[j] = id[id[j]];
            }
            if (i == j) {
                continue;
            }
            if (sz[i] < sz[j]) {
                id[i] = j;
                sz[j] += sz[i];
            }else {
                id[j] = i;
                sz[i] += sz[j];
            }
            unionCount++;
            edges++;
        }
        printf("N: %d, total edges num: %d\n", N, edges);
    }
    return 0;
}

//输出
// N: 1000, total edges num: 999
// N: 10000, total edges num: 9999
// N: 10000, total edges num: 9999
// N: 100000, total edges num: 99999
// N: 1000000, total edges num: 999999